package com.demo06.qsort;

/**
 * @Author: root
 * @Date: 2018/11/14 2:53
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 20, 7, 15, 0, 19, 1, 17, 30, 18, -1, 21};
        f(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    private static void f(int[] arr, int first, int end) {
        if (first < end) {
            int i = qSort(arr, first, end);
            f(arr, first, i - 1);
            f(arr, i + 1, end);
        }
    }

    private static int qSort(int[] arr, int first, int end) {
        int x = arr[first];
        int i = first, j = end;
        while (i < j) {
            while (i < j && x <= arr[j]) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && x > arr[i]) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = x;
        return i;
    }
}
